package mess;

import java.util.Arrays;

public class LeeCode_1139 {
    public static void main(String[] args) {
        int[][] grid = new int[][]{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
//        System.out.println(largest1BorderedSquare(grid));
//        System.out.println(largest1BorderedSquare(new int[][]{{1,1,0,0}}));
     /*   System.out.println(largest1BorderedSquare(new int[][]{{0,1,0,1,1},{1,1,1,1,1},{1,1,0,1,1},
                {1,1,1,1,0},{0,1,1,1,1},{1,1,1,0,1},{0,1,1,1,1},{1,1,1,0,1}}
        ));*/
       /* [[1,1,1,1,1,1,1,0],[1,1,1,1,1,0,1,1],[1,1,1,0,0,1,1,1],
        [1,0,1,1,1,0,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,1,0,1,1],
        [0,1,0,0,0,0,1,1],[1,1,1,1,0,1,1,0],[1,1,0,1,1,1,1,1]]*/

        System.out.println(largest1BorderedSquare(new int[][]{{1, 1, 1, 1, 1, 1, 1, 0}, {1, 1, 1, 1, 1, 0, 1, 1},
                {1, 1, 1, 0, 0, 1, 1, 1}, {1, 0, 1, 1, 1, 0, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 0, 1, 1},
                {0, 1, 0, 0, 0, 0, 1, 1}, {1, 1, 1, 1, 0, 1, 1, 0}, {1, 1, 0, 1, 1, 1, 1, 1}}));
    }

    private static int largest1BorderedSquare(int[][] grid) {
        int len1 = grid.length;
        if (len1 == 0)
            return 0;
        int len2 = grid[0].length;

        int[] start = new int[2];
        //start存在与否的标志
        boolean flag = false;
        int board = 0;
        int max = 0;

        for (int i = 0; i < len1; i++) {
            flag = false;
            for (int j = 0; j < len2; j++) {
                if (len2 - j <= max || len1 - i <= max)
                    continue;
                int num = grid[i][j];
                //未有start, 找到start
                if (num == 1 && !flag) {
                    start[0] = i;
                    start[1] = j;
                    flag = true;
                    board = 1;
                    max = Math.max(max, board);
                }
                //已有start, 向下探索
                if (flag) {
                    int temp = board;
                    while (start[0] + temp < len1 && start[1] + temp < len2) {
                        boolean flag2 = true;
                        //上行: start行不变找列
                        for (int m = start[1] + 1; m <= start[1] + temp; m++) {
                            if (grid[start[0]][m] != 1) {
                                //消除start
                                flag = false;
                                break;
                            }
                        }
                        if (!flag) {
                            break;
                        }
                        //右列: 列不变找行
                        for (int m = start[0] + 1; m <= start[0] + temp; m++) {
                            if (grid[m][start[1] + temp] != 1) {
                                flag2 = false;
                                break;
                            }
                        }
                        if (!flag2) {
                            temp++;
                            continue;
                        }
                        //下行: 行不变找列
                        for (int m = start[1] + temp - 1; m >= start[1]; m--) {
                            if (grid[start[0] + temp][m] != 1) {
                                flag2 = false;
                                break;
                            }
                        }
                        if (!flag2) {
                            temp++;
                            continue;
                        }
                        //左列: 列不变找行
                        for (int m = start[0] + temp - 1; m > start[0]; m--) {
                            if (grid[m][start[1]] != 1) {
                                flag2 = false;
                                break;
                            }
                        }
                        if (!flag2) {
                            temp++;
                            continue;
                        }
                        //满足边长为board + 1
                        temp++;
                        max = Math.max(max, temp);
                    }
                    //start探索完毕, 消除start
                    flag = false;
                }
            }
        }
        return max * max;
    }
}
